The present invention relates to a data compression method of compressing multidimensional data such as 3-D volume data.
Extensive studies have been made on high-efficiency communications of speech and image data as a main theme in multimedia communications. Virtual reality and remote cooperative scientific simulations must be realized in communications of multidimensional (3-D or more), multivariate data
In particular, if high-speed communication networks of Gbit/s class are available, large-scale data accesses will be frequently performed in such a manner that 3-D structure data of genes, molecules, and atoms are referred to for medical drug design, and voxels obtained from tomograms in "CT-scan" and nuclear magnetic resonance are referred to for remote medical diagnosis.
To generate and transfer multidimensional data of several hundreds of Mbytes at a maximum resolution, like data processed in the state-of-the-art scientific simulations, requires almost the communication band of a high-speed supercomputer bus.
Demand has arisen for developing a compression procedure which utilizes the characteristics of multidimensional scientific data.
In 3-D entertainment oriented games, most geometrical objects are represented by polygon sets.
The handling of polygons is highly optimized in the hardware of graphic workstations.
Although studies on high-speed processing by hardware at graphic workstations have been extensively made, 3-D scientific simulation outputs are not ordinarily represented as polygon sets, but are often represented as volume data in its original form, such as the 3-D scalar array .rho.(I,J,K).
The volume data include scalar data of density and temperature, vector data of velocity field and electromagnetic field, and nuclear magnetic resonance voxel data in the medical field. Most of the 3-D scientific data are represented not as polygons but as volume data.
These large data can be used as one of the important media in a multimedia network environment if the standard representation and efficient compression method of the volume data are available.
Techniques for compressing these data are a run-length method applied in facsimile transmission and discrete cosine transformation used in 2-D image compression.
In compressing image data represented in a 3-D array, a 2-D compression method may be expanded to a 3-D method.
A method of generating sampling points using particle coordinates (arranging particles) can also be proposed. According to this method, as for 3-D data, a process of motion of a sphere or particle having a predetermined radius is calculated on the basis of a force acting between two particles, and the coordinates of the center of the sphere in the force balanced equilibrium are defined as a sampling point position.
In the conventional arrangement as described above, when the technique used in 2-D image compression is directly used for 3-D compression, the complexity in algorithm greatly changes between the 2-D compression and the 3-D compression.
In the conventional compression, the correlation between adjacent data is used, but the order of these data poses a problem.
When the dimensionality increases, like 3-D, 4-D, . . . , the direction and the number of adjacent data also increase. It is difficult to apply this conventional compression technique unless the adjacent data are regularly arranged.
It is, for example, difficult to define adjacent volume data of non-structural grids, such as a polygon structure. In this case, it is difficult to apply the above technique.
In these conventional techniques, continuous control cannot be performed because the size of elements is fixed.
No consideration is made for an effective re-division method in the above conventional techniques.
In a conventional case, when a given parameter (determination condition) is designated, input data is compressed at a compression ratio of 50% to 70%. In the conventional case, the compression ratio cannot be specified to a specific value such as 50%.
The sampling point generation procedure using particle coordinates is effective to uniformly distribute sampling points within a given region. However, this procedure is not a procedure for adaptively arranging sampling points so as to regulate the resolution of a specific region.